Рекурсивный спуск
Алгоритм рекурсивного спуска Алгоритм рекурсивного спуска -- это простейший способ разбора текста. При помощи него можно, особо не задумываясь, разобрать, например, арифметическое выражение. Основная идея заключается в том, чтобы разнести разбор разных операций (с разным приоритетом) по разным взаимно-рекурсивным функциям. Тогда, с точки зрения каждой из них, выражение представляет собой набор каких-то левых кусков текста, скреплённых знаками. Содержимое этих кусков функцию не волнует, так как его она разбирать не должна - этим займутся другие, более высокоприоритетные функции. Например, с точки зрения функции, разбирающей операции сложения и вычитания (очевидно, что они имеют равный приоритет), выражение выглядит так: := + | - Это самое простое определение, которое, тем не менее, обладает одним существенным недостатком. Оно неверное. Причина проста: оно утверждает, что операции ( + ) и ( - ) правоассоциативны, однако это верно только по отношению к сложению. Совершенно очевидно, что вычитание следует рассматривать как левоассоциативную операцию. Любой нормальный человек скажет, что 1 - 1 - 1 = (1 - 1) - 1 = -1 Однако, следуя данному выше определению, получаем, что 1 - 1 - 1 = 1 - (1 - 1) = 1 что сомнительно. Таким образом, следует переписать приведённое выше определение как := + | - Грамматика арифметических выражений Итак, с ассоциативностью разобрались. Теперь можно привести полную грамматику, описывающую арифметические выражения. Обозначения операций: ( + ), ( - ), ( * ), ( / ), ( ^ ), - стандартны. := + | - // expr = expression - выражение := * | / // term - одночлен := ^ // powr = power - степень; эта операция правоассоциативна := - | | () // ну а дальше -- просто трюк для представления чисел := | := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 После такого описания грамматики программа, реализующая её разбор, становится весьма очевидной. Разбор арифметических выражений type tree = | Num of int | Minus of tree | Add of tree * tree | Mul of tree * tree | Sub of tree * tree | Div of tree * tree | Pow of tree * tree let parse s = let int_of_ascii x = int_of_char x - 48 and s = s ^ ";" and i = ref 0 in let parse_num () = let rec pn acc = match s.!i with |'0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x)) |_ -> Num acc in pn 0 in let rec parse_expr () = let rec pe acc = match s.!i with |'+' -> incr i; pe (Add (acc, parse_term ())) |'-' -> incr i; pe (Sub (acc, parse_term ())) | _ -> acc in pe (parse_term ()) and parse_term () = let rec pt acc = match s.!i with |'*' -> incr i; pt (Mul (acc, parse_powr ())) |'/' -> incr i; pt (Div (acc, parse_powr ())) | _ -> acc in pt (parse_powr ()) and parse_powr () = let atom = parse_atom () in match s.!i with |'^' -> Pow (atom, parse_powr ()) | _ -> atom in and parse_atom () = match s.!i with '0'..'9' -> parse_num i |'-' -> incr i; Minus (parse_atom ()) |'(' -> incr i; let t = parse_expr () in if s.!i <> ')' then failwith ")" else incr i; t |_ -> failwith "?!!" in let result = parse_expr () in if s.!i <> ';' then failwith "?!!" else result Грамматика лямбды L := app \.L | app app := app term term := (L) | L := \.L | app app := term L | term term := (L) | Разбор лямбды type lambda = | Var of string | App of lambda * lambda | Abs of string * lambda let parse s = let between x a b = (a <= x) && (x <= b) in let is_char x = (between x 'a' 'z') || (between x '0' '9') || (x = char_of_int 39) and s = s ^ ";" and i = ref 0 in let parse_var () = let rec pv acc = match s.!i with |x when is_char x -> incr i; pv (acc ^ (String.make 1 x)) |'.' | ' ' | ')' | ';' -> acc |_ -> failwith "unexpected symbol" in pv "" in let rec parse_expr full = match s.!i with |'\\' -> incr i; let x = parse_var () in Abs (x, parse_expr true) |'.' -> incr i; parse_expr true |'(' -> incr i; let t = parse_expr true in if s.!i <> ')' then failwith ")" else (incr i; if full then parse_app t else t) |';' -> failwith "end of line reached unexpectedly" | _ -> let t = parse_var () in if full then parse_app (Var t) else Var t and parse_app acc = match s.!i with |' ' -> incr i; let t = parse_expr false in parse_app (App (acc, t)) | _ -> acc in parse_expr true Категория:Программирование